# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# 使用列表和字典都可以，字典更快查找
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        cur = head
        a = list()
        if not head:
            return False

        while cur.next:
            if cur in a: 
                return True
            a.append(cur)
            cur = cur.next
        
        return False


# 优化空间复杂度
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        """ 使用快慢指针，就像操场跑步，如果有环的话，慢指针一定能追上快指针 """
        if not head or not head.next:
            return False
        
        slow = head
        fast = head.next

        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        
        return True